package interview.suffixtree;

import interview.common.NnaryTreeNode;

import java.util.ArrayList;

public class SuffixTree {
	public NnaryTreeNode buildSuffixTree(String s) {
		NnaryTreeNode root = new NnaryTreeNode();
		root.setParentEdgeLabel("");
		root.setPosition(-1);

		char[] array = (s + "$").toCharArray();
		int length = array.length;
		for (int i = 0; i < array.length; i++) {
			NnaryTreeNode tmpRoot = root;
			int index = i;

			while (true) {
				ArrayList<NnaryTreeNode> children = tmpRoot.getChildren();
				int nonMatchPoint = 0;
				boolean completeMatch = false;
				NnaryTreeNode matchNode = null;

				for (NnaryTreeNode node : children) {
					char[] label = node.getParentEdgeLabel().toCharArray();
					while (index < length && nonMatchPoint < label.length && label[nonMatchPoint] == array[index]) {
						nonMatchPoint++;
						index++;
						matchNode = node;
					}
					if(nonMatchPoint == label.length) {
						completeMatch = true;
					}
					if(matchNode != null) {
						break;
					}
				}
				
				if (nonMatchPoint == 0) {

					NnaryTreeNode newNode = new NnaryTreeNode();
					newNode.setParentEdgeLabel(new String(array, i, length - i));
					newNode.setPosition(i);

					children.add(newNode);
					break;
				} else if (completeMatch) {
					tmpRoot = matchNode;
				} else {
					char[] label = matchNode.getParentEdgeLabel().toCharArray();
					
					NnaryTreeNode newLeafNode1 = new NnaryTreeNode();
					newLeafNode1.setParentEdgeLabel(new String(label, nonMatchPoint, label.length - nonMatchPoint));
					newLeafNode1.setPosition(i);
					newLeafNode1.setChildren(matchNode.getChildren());
					
					NnaryTreeNode newLeafNode2 = new NnaryTreeNode();
					newLeafNode2.setParentEdgeLabel(new String(array, index, length - index));
					newLeafNode2.setPosition(i);
					
					ArrayList<NnaryTreeNode> newChildren = new ArrayList<NnaryTreeNode>();
					newChildren.add(newLeafNode1);
					newChildren.add(newLeafNode2);
					matchNode.setParentEdgeLabel(new String(label, 0, nonMatchPoint));
					matchNode.setChildren(newChildren);
					matchNode.setPosition(-1);
					break;
				}
			}

		}

		return root;
	}
}
